package io.zouyalong.algo.leetcode;

import java.util.Comparator;
import java.util.PriorityQueue;
import java.util.Queue;

class MKListNode {
    int val;
    MKListNode next;

    MKListNode(int x) {
        val = x;
    }
}

class MKListNodeComparator implements Comparator<MKListNode> {

    @Override
    public int compare(MKListNode o1, MKListNode o2) {
        if (o1.val > o2.val) {
            return 1;
        }
        if (o1.val == o2.val) {
            return 0;
        }
        return -1;
    }
}

/**
 * https://leetcode-cn.com/problems/merge-k-sorted-lists/solution/
 */
public class MergeKSortedLists {
    public MKListNode solution1(MKListNode[] lists) {
        Queue<MKListNode> queue = new PriorityQueue<>(new MKListNodeComparator());
        for (MKListNode head : lists) {
            if (head != null) {
                queue.offer(head);
            }
        }
        var dummy = new MKListNode(0);
        var tail = dummy;
        for (var current = queue.poll(); current != null; current = queue.poll()) {
            tail.next = current;
            tail = tail.next;
            if (current.next != null) {
                queue.offer(current.next);
            }
        }
        return dummy.next;
    }
}
